package algorithm.poj.p1000;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.URL;
import java.net.URLDecoder;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

/**
 * 分析：
 * 问题的难点是格子中的计算公式虽然不会出现A依赖B，B依赖A的情况，但可能出现
 * A依赖B，B依赖C，C依赖D，而A,B,C,D都是计算公式的情形。
 * 
 * 一般做法是使用拓扑排序，再依次计算。
 * 
 * 实现：
 * 经验：
 * 教训：
 * 分类：拓扑排序 图算法
 * 
 * @author wong.tong@gmail.com
 *
 */
public class P1420 {

	@SuppressWarnings("unchecked")
	public static void main(String[] args) throws Exception {

		InputStream input = null;
		if (false) {
			input = System.in;
		} else {
			URL url = P1420.class.getResource("P1420.txt");
			File file = new File(URLDecoder.decode(url.getPath(), "UTF-8"));
			input = new FileInputStream(file);
		}
		
		BufferedReader stdin = new BufferedReader(new InputStreamReader(input));

		StringBuffer sb = new StringBuffer("");
		StringTokenizer st = null;
		String line = stdin.readLine();
		int T = Integer.valueOf(line.trim());
		for (int i = 0; i < T; i ++) {
			line = stdin.readLine();
			st = new StringTokenizer(line);
			int m = Integer.valueOf(st.nextToken());
			int n = Integer.valueOf(st.nextToken());
			//读入数据
			Cell[][] sheet = new Cell[n][];
			for (int r = 0; r < n; r ++) {
				sheet[r] = new Cell[m];
				line = stdin.readLine();
				st = new StringTokenizer(line);
				for (int c = 0; c < m; c ++) {
					sheet[r][c] = new Cell(r, c, st.nextToken());
				}
			}
			//分析单元格
			for (int r = 0; r < n;  r ++) {
				for (int c = 0; c < m; c ++) {
					Cell cell = sheet[r][c];
					if (cell.formula != null) {
						st = new StringTokenizer(cell.formula, "=+");
						while (st.hasMoreTokens()) {
							int row = 0, col = 0;
							char[] t = st.nextToken().toCharArray();
							for (int k = 0; k < t.length; k ++) {
								if (t[k] >= 'A' && t[k] <= 'Z') {
									col = 26*col + (t[k]-'A'+1);
								} else {
									row = 10*row + (t[k]-'0');
								}
							}
							row --;
							col --;
							
							if (sheet[row][col].formula == null) {
								cell.value += sheet[row][col].value;
							} else {
								cell.dependsOn.add(sheet[row][col]);
								sheet[row][col].dependedBy.add(cell);
							}
						}
					}
				}
			}
			//拓扑排序，同时计算所有计算单元
			LinkedList<Cell> queue = new LinkedList<Cell>();
			for (int r = 0; r < n;  r ++) {
				for (int c = 0; c < m; c ++) {
					if (sheet[r][c].formula != null && sheet[r][c].dependsOn.size() == 0) {
						queue.add(sheet[r][c]);
					}
				}
			}
			while (!queue.isEmpty()) {
				Cell cell = queue.poll();
				for (Cell c: cell.dependedBy) {
					c.value += cell.value;
					c.dependsOn.remove(cell);
					if (c.dependsOn.size() == 0) {
						queue.addLast(c);
					}
				}
			}
			//输出结果
			for (int r = 0; r < n;  r ++) {
				for (int c = 0; c < m; c ++) {
					long value = sheet[r][c].value; 
					if (c == 0) {
						sb.append(value);
					} else {
						sb.append(" ").append(value);
					}
				}
				sb.append("\n");
			}
		}
		System.out.println(sb);
	}
	
	private static class Cell {
		
		int row;
		int col;
		Long value;
		String formula;
		List<Cell> dependsOn;
		List<Cell> dependedBy;
		
		public Cell(int row, int col, String value) {
			
			this.row = row;
			this.col = col;
			this.dependsOn = new ArrayList<Cell>();
			this.dependedBy = new ArrayList<Cell>();
			if (value.charAt(0) == '='){
				this.value = 0L;
				this.formula = value;
			} else {
				this.value = Long.valueOf(value);
			}
		}
		
		public boolean equals(Object obj) {
			if (obj == null || !(obj instanceof Cell)) {
				return false;
			} else {
				Cell cell = (Cell)obj;
				return cell.row == this.row && cell.col == this.col;
			}
		}
		
		public String toString() {
			String str = "C[" +this.row + ", " + this.col + "]=";
			if (this.formula == null) {
				str += this.value;
			} else {
				str += this.formula;
			}
			return str;
		}
	}
	
}